Abstract Algebra:Cayley's Theorem

Let G and H be groups. A function f :G maps

H which satisfies (1) for all g, g' element of

G is called a homomorphism of G into H. If f:G maps

H is a homomorphism. The kernel of f is ker(f) = {x element of

G | f(x) = 1_H}. Let G₁ and G₂ be groups. An isomorphism from G₁ to G₂ is an injection phi

:G₁

G₂ such that phi

(a · b) =

(a) ·

(b) (a,b

G₁ if

is also surjective G₁ is isomorphic to G₂). A function f : A maps

B is said to be injective (or one to one) if whenever f(x) = f(y), we have x = y. A function that is both one-to-one and onto, that is if f(x) = f(y) then x = y, and for every y of the domain there is an x of the range so that f(x) = y. A function f : A maps

B is said to be surjective (or onto) if for every y element of

B there exists x element of

A such that f(x) = y.

Cayley's Theorem

We have stated that on of the main objectives of group theory is to write down a complete list of non-isomorphic groups. At first, such a task appears hopeless. For, as we have seen, groups pop up in some very unexpected places and, therefore, if we set out to compile a list of all non-isomorphic groups, we would hardly begin to know where to look. The following theorem of Cayley solves this dilemma.

Theorem 1: Every group is isomorphic to a subgroup of a permutation group

Proof: Let G be a group, g element of G. define

_g:G

_g(x) = xg^-1 (x element of

G).

If rho _g(x) = rho _g(y), then xg^-1 = yg^-1, so that x = y. Therefore, _g is an injection. If y element of G, then rho _g(yg) = yg · g^-1 = y. Therefore, rho _g is a surjection. Thus, since rho _g is a bijection, rho _g is a permutation of the elements of the set G, and rho _g S_G. Let us consider the mapping

S_G

defined by

(1)

Since rho _gg' = x(gg')^-1 = rho _g rho _g'(x), the mapping (1) is a homomorphism. But rho = 1_{S_G} if and only if x · g = x for all x element of G, which occurs if and only if g = 1_G. Therefore, the kernel of the homomorphism (1) is 1_G, and therefore the mapping (1) is an injection. Thus we have shown that G is isomorphic to a subgroup of S_G.

What Cayley's theorem tells us is that permutation groups and their subgroups are all the groups that can exist. Unfortunately, the problem of classifying the subgroups of a permutation group is extremely complicated, even in the case of a finite permutation group. Therefore, Cayley's theorem does not allow us to easily identify a complete list of groups.

The above argument actually proves somewhat more than claimed. For if G is finite, having order n, then G is isomorphic to a subgroup of S_G. Therefore we have

Corollary 2: If G has finite order n, then G is isomorphic to a subgroup of S_n.